\section{运算及关系}

\subsection{集合和映射的相关内容}

\begin{definition}
	设 $A_0 \subseteq A$，
	定义一个映射$i:A_0 \rightarrow A$，
	使$i(x)=x$， $x \in A_0$，
	则称映射$i$ 为 $A_0$ 到 $A$ 的一个嵌入映射。
\end{definition}

\begin{definition}
	设 $A_0 \subseteq A$，
	$f:A \rightarrow B$ ，
	$g:A_0 \rightarrow B$是映射。
	如果$\forall x \in A_0$，$f(x)=g(x)$，
	则称$f$ 为$g$的开拓，
	$g$为$f$（在$A_0$上）的限制.
	记为 $g = f|_{A_0}$.
\end{definition}

\begin{definition}[满射]
	我们称一个映射$f: A \rightarrow B$是满射，当且仅当任取一个$b \in B$，总存在一个$a \in A$，使得$f(a) = b$。

	换句话讲，一个映射是满射，就说明$B$中的每一个元素都可以找到来源的，也说明$A$的像是充满整个集合$B$的。
\end{definition}

\begin{definition}[单射]
	我们称一个映射$f: A \rightarrow B$是一个单射，当且仅当任取$a_1,a_2 \in A$（$a_1 \ne a_2$），$f(a_1) \ne f(a_2)$。

	单射刻画了像集中的任意元素都最多只能是某一个元素的像；刻画了不同元素的像一定不同。
\end{definition}

\begin{definition}[一一映射（双射）]
	我们称一个映射$f$是一一映射（双射），当且仅当它既是单射又是满射。

	一一映射正如其名，刻画了每个元素都是一一对应的。对定义域中的每一个元素都唯一对应一个像。
\end{definition}

那么接下来有一个非常重要的命题，我们常常用此来证明两个有限集的阶相同。

\begin{theorem}
	如果有限集$A$和$B$之间存在一个一一映射$f:A \rightarrow B$，那么$|A|=|B|$。
\end{theorem}

\begin{proof}
	首先，鉴于$f$是一个单射，也就是任取不同的元素，其对应的像也不同，那么显然这就要求$|A| \le |B|$；
	另一方面，鉴于$f$是一个满射，这说明任何一个$B$中的元素都有其原像，这显然说明$|B| \le |A|$。
	综合以上两点，命题得证。
\end{proof}

\begin{definition}
	交换图\ \ \ 略
\end{definition}

\begin{definition}
	有集合$A$, $B$，令$A\times B = \{(a,b) | a \in A, b \in B  \}$，
	称$A \times B$是$A, B$ 的直积。

	类似的，我们可以定义多个集合的直积。
\end{definition}

\subsection{运算和运算规律}

\begin{definition}
	有非空集合$A,B,D$，
	一个映射$f:A\times B\rightarrow D$
	称为$A$与$B$到$D$的一个代数运算。

	如果$A=B=D$，
	则称$f$ 是定义在$A$（$B$、$D$）上的一个二元运算。
\end{definition}

\begin{definition}
	设 $A$ 上有二元运算，满足
	$\forall x,y \in A$，$xy=yx$，
	则称该运算满足交换律。
\end{definition}

\begin{definition}
	设 $A$ 上有二元运算，满足
	$\forall x,y,z \in A$，$(xy)z=x(yz)$，
	则称该运算满足结合律。
\end{definition}

\begin{definition}
	设 $A$ 上有两个二元运算$\circ$、$+$，满足
	$\forall x,y,z \in A$，
	$x \circ (y + z) = x \circ y + x \circ z$，
	则称满足“$\circ$”对“$+$”的左分配律。

	同理能定义右分配律。左、右分配律统称分配率。
\end{definition}

\subsubsection{运算表}

有运算 $f:A \times B \rightarrow D$，
当 $A$ 和 $B$都有限时，我们可以打一个表来表示运算的结果。

$$
	\begin{matrix}
		\circ   & b_1    & b_2    & \cdots & b_{|B|} \\
		a_1     & ?      & ?      & \cdots & ?       \\
		a_2     & ?      & ?      & \cdots & ?       \\
		\vdots  & \vdots & \vdots & \ddots & ?       \\
		a_{|A|} & ?      & ?      & \cdots & ?       \\
	\end{matrix}
$$

\subsection{构造新集合的方法——关系和等价关系}

\begin{definition}
	设非空集合$A$，
	$A$ 中的一个关系 $R \subseteq A \times A$；
	如果$a \in A, b \in A$，且$(a,b) \in R$，
	则称$a, b$ 具有关系 $R$，记作$a\ R\ b$。
\end{definition}

\begin{definition}
	在非空集合 $A$ 里面定义了一个关系 $R$，
	如果$R$满足以下条件：
	\begin{itemize}
		\item \textbf{\heiti 反身性：}$\forall a \in A$，$aRa$。
		\item \textbf{\heiti 对称性：}$\forall a,b \in A$，$aRb \Leftrightarrow bRa$。
		\item \textbf{\heiti 传递性：}$\forall a,b,c \in A$，$aRb, bRc \Rightarrow a R c$。
	\end{itemize}
	则称$R$ 为一个等价关系。
\end{definition}

\begin{definition}
	非空集合$A$的一个分划是指：一个由$A$的某些子集组成的集合，
	使得任取$A$ 中的一个元素，其包含且只包含在其中一个子集里面。

	换言之：$A$中的一个划分是指将$A$写成一些不相交的非空子集的并。

	用符号语言来说，满足以下条件的集合 $\{A_i \subsetneqq A \mid i \in I\}$
	是 $A$ 的一个分划：
	\begin{itemize}
		\item $A = \bigcup\limits_{i \in I}A_i$
		\item $\forall i \in I$，$A_i \ne \varnothing$
		\item $\forall i, j \in I$，$i \ne j$，$A_i \cap A_j = \varnothing$
	\end{itemize}

\end{definition}

\begin{theorem}
	$A$ 的一个分类决定 $A$ 中一个等价关系。
\end{theorem}

\begin{proof}
	设 $A = \bigcup\limits_{i \in I}A_i$，$A_i \ne \varnothing$，$A_i \cap A_j = \varnothing$。
	定义关系 $R: aRb \Leftrightarrow \exists i \in I, a, b \in A_i$。
	显然，关系$R$满足反身性、对称性、传递性，这说明关系$R$是一个等价关系。
\end{proof}

\begin{definition}
	设非空集合$A$ 中有一个等价关系 $R$，$a\in A$。
	定义 $a$ 的等价类 $\bar{a} = \{b \in A \mid a R b \}$
\end{definition}

\begin{definition}
	设非空集合$A$ 中有一个等价关系 $R$。
	定义集合 $A/R = \{ \bar{a} \mid a \in A \}$ 为$A$对$R$的商集。
\end{definition}

\begin{definition}
	设非空集合$A$ 中有一个等价关系 $R$。
	映射 $\pi: A \rightarrow A/R$满足$\pi(a)=\bar{a}$，$a\in A$
	称为$A$ 到 $A/R$ 的一个自然映射。
\end{definition}

\begin{theorem}
	$A$ 中的一个等价关系 $R$ 决定 $A$ 的一个分类。
\end{theorem}

\begin{proof}
	$A/R$ 就是分类。对于任意的$\bar{a} \in A/R$：
	首先，$\bar{a} \subseteq A$，$\bar{a} \ne \varnothing$；
	$A = \bigcup\limits_{i \in I}A_i$；
	接下来证明$\forall \bar{a}, \bar{b} \in A/R$，$\bar{a} \ne \bar{b}$，$\bar{a} \cap \bar{b} = \varnothing$，
	采用反证法，如果$\bar{a} \cap \bar{b} \ne \varnothing$，取 $ c \in \bar{a} \cap \bar{b}$，
	$c \in \bar{a} \Rightarrow cRa$，
	$c \in \bar{b} \Rightarrow cRb$，
	$cRa \wedge cRb \Rightarrow aRb$，
	因此$\bar{a} = \bar{b}$，矛盾。
	因此$A/R$ 是一个分类。
\end{proof}

\begin{definition}
	设非空集合$A$ 中有一个等价关系 $R$和二元运算$\circ$，
	如果$R$ 和$\circ$ 满足条件：
	$$
		a_1 R b_1 , a_2 R b_2 \Rightarrow a_1\circ a_2 R b_1 \circ b_2
	$$
	则称 $R$ 为 $\circ$ 的同余关系。
\end{definition}
